package ks;

import java.util.Scanner;

public class Main {
    /**
     *
     */
    public final static int INFINITY = Integer.MAX_VALUE;
    public static int[] a = new int[2];

    public static void main(String[] args) throws Exception {
        csyz();
        Scanner sc = new Scanner(System.in);
        System.out.print("请输入进货时间：");
        double time = sc.nextDouble();
        if ((time >= 8 && time <= 11.4) || (time >= 14 && time <= 17.4) || (time >= 19 && time <= 20.3)) {
            System.out.println("上课时间时所走的路线：");
            timelx1();

        } else if ((time > 11.4 && time < 14) || (time > 17.4 && time < 19) || (time > 20.3 && time < 22)) {
            System.out.println("下课时间时所走的路线：");
            timelx();
        } else {
            System.out.println("你输入的时间无配送，请重新输入");
            time = sc.nextDouble();
            if ((time > 11.4 && time < 14) || (time > 17.4 && time < 19) || (time > 20.3 && time < 22)) {
                System.out.println("下课时间时所走的路线：");
                timelx();
            } else {
                System.out.println("上课时间时所走的路线：");
                timelx1();
            }
        }

    }

    public static void csyz() throws Exception {
        // 超市选址
        Object vexs[] = { "二食堂", "办公楼", "教学楼", "一舍", "十舍", "图书馆", "体育馆", "大门" };
        int[][] arce = { { 0, INFINITY, INFINITY, 15, 30, INFINITY, 10, 12 },
                { INFINITY, 0, INFINITY, INFINITY, 4, 4, INFINITY, INFINITY },
                { INFINITY, INFINITY, 0, 4, INFINITY, 6, INFINITY, 10 },
                { 15, INFINITY, 4, 0, INFINITY, INFINITY, 20, INFINITY },
                { 30, 4, INFINITY, INFINITY, 0, 12, 8, INFINITY },
                { INFINITY, 4, 6, INFINITY, 12, 0, INFINITY, INFINITY },
                { 10, INFINITY, INFINITY, 20, 8, INFINITY, 0, INFINITY },
                { 12, INFINITY, 10, INFINITY, INFINITY, INFINITY, INFINITY, 0 } };
        MGraph G = new MGraph(GraphKind.UDG, 8, 12, vexs, arce);
        ShortestPath_FLOYD floyd = new ShortestPath_FLOYD();
        floyd.floyd(G);
        System.out.println("校园路径图为：");
        pmt(G);
        System.out.println("超市选址为：");
        findPlace(G, floyd.getD());
    }

    public static void findPlace(MGraph G, int[][] D) throws Exception {
        int min = INFINITY;
        int sum = 0;
        int u = -1;
        int d = D.length;
        for (int v = 0; v < d; v++) {
            sum = 0;
            for (int w = 0; w < d; w++)
                sum += D[v][w]; // 求一点到其他顶点的最短长度之和
            if (min > sum) {
                min = sum;
                u = v;
            }

        }
        int s = u;
        if (s == 2) {
            System.out.println("最佳选址为教学楼，不能建超市已为你重新规划选址！");
        }
        if (s == 3) {
            System.out.println("最佳选址为一舍，临近教学楼不能建超市已为你重新规划选址！");
        }
        if (s == 5) {
            System.out.println("最佳选址为图书馆，临近教学楼不能建超市已为你重新规划选址！");
        }
        if (s == 7) {
            System.out.println("最佳选址为大门，不能建超市已为你重新规划选址！");
        }
        int min2 = INFINITY;
        int sum2 = 0;
        int k = -1;
        int b = D.length;
        for (int v = 0; v < b; v++) {
            sum2 = 0;
            for (int w = 0; w < b; w++)
                sum2 += D[v][w]; // 求一点到其他顶点的最短长度之和
            if (min2 > sum2 && v != 2 && v != 3 && v != 5 && v != 7) {
                min2 = sum2;
                k = v;
            }

        }
        System.out.println("超市应设在 " + G.getVex(k) + " ,到其他各点的最短路径距离依次为：");
        if (G.getVex(k) == "二食堂") {
            a[0] = 1;

        }
        if (G.getVex(k) == "办公楼") {
            a[0] = 2;

        }
        if (G.getVex(k) == "十舍") {
            a[0] = 3;

        }
        if (G.getVex(k) == "体育馆") {
            a[0] = 4;

        }

        for (int i = 0; i < d; i++)
            System.out.print(D[k][i] + "\t");
        System.out.println();

    }

    public static void timelx1() throws Exception {
        Object vexs[] = { "二食堂", "办公楼", "十舍", "体育馆", "大门" };
        int index = vexs.length;
        int[][] arcs = new int[index][index];
        int[] v0 = { 0, INFINITY, INFINITY, 10, 12 };
        int[] v1 = { INFINITY, 0, 4, INFINITY, INFINITY };
        int[] v2 = { INFINITY, 4, 0, 8, INFINITY };
        int[] v3 = { 10, INFINITY, 8, 0, INFINITY };
        int[] v4 = { 12, INFINITY, INFINITY, INFINITY, 0 };
        arcs[0] = v0;
        arcs[1] = v1;
        arcs[2] = v2;
        arcs[3] = v3;
        arcs[4] = v4;
        MGraph G = new MGraph(GraphKind.UDG, 5, 15, vexs, arcs);
        ShortestPath_FLOYD floyd = new ShortestPath_FLOYD();
        floyd.floyd(G);
        print(G, floyd.getW(), floyd.getD());
    }

    public static void timelx() throws Exception {
        Object vexs[] = { "办公楼", "教学楼", "十舍", "图书馆", "体育馆", "大门" };
        int index = vexs.length;
        int[][] arcs = new int[index][index];
        int[] v0 = { 0, INFINITY, 4, 4, INFINITY, INFINITY };
        int[] v1 = { INFINITY, 0, INFINITY, 6, INFINITY, 10 };
        int[] v2 = { 4, INFINITY, 0, 12, 8, INFINITY };
        int[] v3 = { 4, 6, 12, 0, INFINITY, INFINITY };
        int[] v4 = { INFINITY, INFINITY, 8, INFINITY, 0, INFINITY };
        int[] v5 = { INFINITY, 10, INFINITY, INFINITY, INFINITY, 0 };
        arcs[0] = v0;
        arcs[1] = v1;
        arcs[2] = v2;
        arcs[3] = v3;
        arcs[4] = v4;
        arcs[5] = v5;
        MGraph G = new MGraph(GraphKind.UDG, 6, 15, vexs, arcs);
        ShortestPath_FLOYD floyd = new ShortestPath_FLOYD();
        floyd.floyd(G);
        print(G, floyd.getW(), floyd.getD());
    }

    public static void print(MGraph G, int[][] W, int[][] D) throws Exception {
        int m = 0, n = 0;

        for (int i = 0; i < G.getVexs().length; i++) {
            if (G.getVex(i) == "大门")
                m = i;
            if (a[0] == 1) {
                if (G.getVex(i) == "二食堂")
                    n = i;
            }
            if (a[0] == 2) {
                if (G.getVex(i) == "办公楼")
                    n = i;
            }
            if (a[0] == 3) {
                if (G.getVex(i) == "十舍")
                    n = i;
            }
            if (a[0] == 4) {
                if (G.getVex(i) == "体育馆")
                    n = i;
            }
        }
        System.out.print("起始点为：");
        int k = W[m][n];
        System.out.println("大门-->" + G.getVex(n) + "\t最短路径距离为：" + D[m][n]);
        System.out.print("具体路径为：");
        System.out.print(G.getVex(m));
        while (k != n) {
            System.out.print("-->" + G.getVex(k));
            k = W[k][n];
        }
        System.out.print("-->" + G.getVex(n));
    }

    public static void pmt(MGraph G) throws Exception {
        for (int v = 0; v < 8; v++) {
            for (int w = 0; w < 8; w++) {
                if (G.getArcs()[v][w] != INFINITY && G.getArcs()[v][w] != 0) {
                    System.out.println(G.getVex(v) + " 到 " + G.getVex(w) + G.getArcs()[v][w]);
                }
            }

        }
    }
}
